The INTERNET, and in particular, the World-Wide Web (WWW), is growing in popularity and usage for both commercial and recreational purposes, and this trend is expected to continue. This phenomenon is being driven, in part, by the increasing and widespread use of personal computer systems and the availability of low cost INTERNET access.
The emergence of inexpensive INTERNET access devices and high speed access techniques such as ADSL, cable modems, satellite modems, and the like, are expected to further accelerate the mass usage of the WWW.
Accordingly, it is expected that the number of entities offering services, products, etc., over the WWW will increase dramatically over the coming years. Until now, however, the INTERNET “experience” for users has been limited mostly to non-voice based input/output devices, such as keyboards, intelligent electronic pads, mice, trackballs, printers, monitors, etc. This presents somewhat of a bottleneck for interacting over the WWW for a variety of reasons.
First, there is the issue of familiarity. Many kinds of applications lend themselves much more naturally and fluently to a voice-based environment. For instance, most people shopping for audio recordings are very comfortable with asking a live sales clerk in a record store for information on titles by a particular author, where they can be found in the store, etc. While it is often possible to browse and search on one's own to locate items of interest, it is usually easier and more efficient to get some form of human assistance first, and, with few exceptions, this request for assistance is presented in the form of a oral query. In addition, many persons cannot or will not, because of physical or psychological barriers, use any of the aforementioned conventional I/O devices. For example, many older persons cannot easily read the text presented on WWW pages, or understand the layout/hierarchy of menus, or manipulate a mouse to make finely coordinated movements to indicate their selections. Many others are intimidated by the look and complexity of computer systems, WWW pages, etc., and therefore do not attempt to use online services for this reason as well.
Thus, applications which can mimic normal human interactions are likely to be preferred by potential on-line shoppers and persons looking for information over the WWW. It is also expected that the use of voice-based systems will increase the universe of persons willing to engage in e-commerce, e-learning, etc. To date, however, there are very few systems, if any, which permit this type of interaction, and, if they do, it is very limited. For example, various commercial programs sold by IBM (VIAVOICE™) and Kurzweil (DRAGON™) permit some user control of the interface (opening, closing files) and searching (by using previously trained URLs) but they do not present a flexible solution that can be used by a number of users across multiple cultures and without time consuming voice training. Typical prior efforts to implement voice based functionality in an INTERNET context can be seen in U.S. Pat. No. 5,819,220 incorporated by reference herein.
Another issue presented by the lack of voice-based systems is efficiency. Many companies are now offering technical support over the INTERNET, and some even offer live operator assistance for such queries. While this is very advantageous (for the reasons mentioned above) it is also extremely costly and inefficient, because a real person must be employed to handle such queries. This presents a practical limit that results in long wait times for responses or high labor overheads. An example of this approach can be seen U.S. Pat. No. 5,802,526 also incorporated by reference herein. In general, a service presented over the WWW is far more desirable if it is “scalable,” or, in other words, able to handle an increasing amount of user traffic with little if any perceived delay or troubles by a prospective user.
In a similar context, while remote learning has become an increasingly popular option for many students, it is practically impossible for an instructor to be able to field questions from more than one person at a time. Even then, such interaction usually takes place for only a limited period of time because of other instructor time constraints. To date, however, there is no practical way for students to continue a human-like question and answer type dialog after the learning session is over, or without the presence of the instructor to personally address such queries.
Conversely, another aspect of emulating a human-like dialog involves the use of oral feedback. In other words, many persons prefer to receive answers and information in audible form. While a form of this functionality is used by some websites to communicate information to visitors, it is not performed in a real-time, interactive question-answer dialog fashion so its effectiveness and usefulness is limited.
Yet another area that could benefit from speech-based interaction involves so-called “search” engines used by INTERNET users to locate information of interest at web sites, such as the those available at YAHOO®.com, METACRAWLER®.com, EXCITE®.com, etc. These tools permit the user to form a search query using either combinations of keywords or metacategories to search through a web page database containing text indices associated with one or more distinct web pages. After processing the user's request, therefore, the search engine returns a number of hits which correspond, generally, to URL pointers and text excerpts from the web pages that represent the closest match made by such search engine for the particular user query based on the search processing logic used by search engine. The structure and operation of such prior art search engines, including the mechanism by which they build the web page database, and parse the search query, are well known in the art. To date, applicant is unaware of any such search engine that can easily and reliably search and retrieve information based on speech input from a user.
There are a number of reasons why the above environments (e-commerce, e-support, remote learning, INTERNET searching, etc.) do not utilize speech-based interfaces, despite the many benefits that would otherwise flow from such capability. First, there is obviously a requirement that the output of the speech recognizer be as accurate as possible. One of the more reliable approaches to speech recognition used at this time is based on the Hidden Markov Model (HMM)—a model used to mathematically describe any time series. A conventional usage of this technique is disclosed, for example, in U.S. Pat. No. 4,587,670 incorporated by reference herein. Because speech is considered to have an underlying sequence of one or more symbols, the HMM models corresponding to each symbol are trained on vectors from the speech waveforms. The Hidden Markov Model is a finite set of states, each of which is associated with a (generally multi-dimensional) probability distribution. Transitions among the states are governed by a set of probabilities called transition probabilities. In a particular state an outcome or observation can be generated, according to the associated probability distribution. This finite state machine changes state once every time unit, and each time t such that a state j is entered, a spectral parameter vector Ot is generated with probability density Bj(Ot). It is only the outcome, not the state visible to an external observer and therefore states are “hidden” to the outside; hence the name Hidden Markov Model. The basic theory of HMMs was published in a series of classic papers by Baum and his colleagues in the late 1960's and early 1970's. HMMs were first used in speech applications by Baker at Carnegie Mellon, by Jelenik and colleagues at IBM in the late 1970's and by Steve Young and colleagues at Cambridge University, UK in the 1990's. Some typical papers and texts are as follows:                1. L. E. Baum, T. Petrie, “Statistical inference for probabilistic functions for finite state Markov chains”, Ann. Math. Stat., 37: 1554-1563, 1966        2. L. E. Baum, “An inequality and associated maximation technique in statistical estimation for probabilistic functions of Markov processes”, Inequalities 3: 1-8, 1972        3. J. H. Baker, “The dragon system—An Overview”, IEEE Trans. on ASSP Proc., ASSP-23(1): 24-29, Feb. 1975        4. F. Jeninek et al, “Continuous Speech Recognition: Statistical methods” in Handbook of Statistics, II, P. R. Kristnaiad, Ed. Amsterdam, The Netherlands, North-Holland, 1982        5. L. R. Bahl, F. Jeninek, R. L. Mercer, “A maximum likelihood approach to continuous speech recognition”, IEEE Trans. Pattern Anal. Mach. Intell., PAMI-5: 179-190, 1983        6. J. D. Ferguson, “Hidden Markov Analysis: An Introduction”, in Hidden Markov Models for Speech, Institute of Defense Analyses, Princeton, N.J. 1980.        7. H. R. Rabiner and B. H. Juang, “Fundamentals of Speech Recognition”, Prentice Hall, 1993        8. H. R. Rabiner, “Digital Processing of Speech Signals”, Prentice Hall, 1978        
More recently research has progressed in extending HMM and combining HMMs with neural networks to speech recognition applications at various laboratories. The following is a representative paper:                9. Nelson Morgan, Hervé Bourlard, Steve Renals, Michael Cohen and Horacio Franco (1993), Hybrid Neural Network/Hidden Markov Model Systems for Continuous Speech Recognition. Journal of Pattern Recognition and Artificial Intelligence, Vol. 7, No. 4 pp. 899-916. Also in I. Guyon and P. Wang editors, Advances in Pattern Recognition Systems using Neural Networks, Vol. 7 of a Series in Machine Perception and Artificial Intelligence. World Scientific, February 1994.        
All of the above are hereby incorporated by reference. While the HMM-based speech recognition yields very good results, contemporary variations of this technique cannot guarantee a word accuracy requirement of 100% exactly and consistently, as will be required for WWW applications for all possible all user and environment conditions. Thus, although speech recognition technology has been available for several years, and has improved significantly, the technical requirements have placed severe restrictions on the specifications for the speech recognition accuracy that is required for an application that combines speech recognition and natural language processing to work satisfactorily.
In contrast to word recognition, Natural language processing (NLP) is concerned with the parsing, understanding and indexing of transcribed utterances and larger linguistic units. Because spontaneous speech contains many surface phenomena such as disfluencies, —hesitations, repairs and restarts, discourse markers such as ‘well’ and other elements which cannot be handled by the typical speech recognizer, it is the problem and the source of the large gap that separates speech recognition and natural language processing technologies. Except for silence between utterances, another problem is the absence of any marked punctuation available for segmenting the speech input into meaningful units such as utterances. For optimal NLP performance, these types of phenomena should be annotated at its input. However, most continuous speech recognition systems produce only a raw sequence of words. Examples of conventional systems using NLP are shown in U.S. Pat. Nos. 4,991,094, 5,068,789, 5,146,405 and 5,680,628, all of which are incorporated by reference herein.
Second, most of the very reliable voice recognition systems are speaker-dependent, requiring that the interface be “trained” with the user's voice, which takes a lot of time, and is thus very undesirable from the perspective of a WWW environment, where a user may interact only a few times with a particular website. Furthermore, speaker-dependent systems usually require a large user dictionary (one for each unique user) which reduces the speed of recognition. This makes it much harder to implement a real-time dialog interface with satisfactory response capability (i.e., something that mirrors normal conversation—on the order of 3-5 seconds is probably ideal). At present, the typical shrink-wrapped speech recognition application software include offerings from IBM (VIAVOICE™) and Dragon Systems (DRAGON™). While most of these applications are adequate for dictation and other transcribing applications, they are woefully inadequate for applications such as NLQS where the word error rate must be close to 0%. In addition these offerings require long training times and are typically are non client-server configurations. Other types of trained systems are discussed in U.S. Pat. No. 5,231,670 assigned to Kurzweil, and which is also incorporated by reference herein.
Another significant problem faced in a distributed voice-based system is a lack of uniformity/control in the speech recognition process. In a typical stand-alone implementation of a speech recognition system, the entire SR engine runs on a single client. A well-known system of this type is depicted in U.S. Pat. No. 4,991,217 incorporated by reference herein. These clients can take numerous forms (desktop PC, laptop PC, PDA, etc.) having varying speech signal processing and communications capability. Thus, from the server side perspective, it is not easy to assure uniform treatment of all users accessing a voice-enabled web page, since such users may have significantly disparate word recognition and error rate performances. While a prior art reference to Gould et al.—U.S. Pat. No. 5,915,236—discusses generally the notion of tailoring a recognition process to a set of available computational resources, it does not address or attempt to solve the issue of how to optimize resources in a distributed environment such as a client-server model. Again, to enable such voice-based technologies on a wide-spread scale it is far more preferable to have a system that harmonizes and accounts for discrepancies in individual systems so that even the thinnest client is supportable, and so that all users are able to interact in a satisfactory manner with the remote server running the e-commerce, e-support and/or remote learning application.
Two references that refer to a distributed approach for speech recognition include U.S. Pat. Nos. 5,956,683 and 5,960,399 incorporated by reference herein. In the first of these, U.S. Pat. No. 5,956,683—Distributed Voice Recognition System (assigned to Qualcomm) an implementation of a distributed voice recognition system between a telephony-based handset and a remote station is described. In this implementation, all of the word recognition operations seem to take place at the handset. This is done since the patent describes the benefits that result from locating of the system for acoustic feature extraction at the portable or cellular phone in order to limit degradation of the acoustic features due to quantization distortion resulting from the narrow bandwidth telephony channel. This reference therefore does not address the issue of how to ensure adequate performance for a very thin client platform. Moreover, it is difficult to determine, how, if at all, the system can perform real-time word recognition, and there is no meaningful description of how to integrate the system with a natural language processor.
The second of these references—U.S. Pat. No. 5,960,399—Client/Server Speech Processor/Recognizer (assigned to GTE) describes the implementation of a HMM-based distributed speech recognition system. This reference is not instructive in many respects, however, including how to optimize acoustic feature extraction for a variety of client platforms, such as by performing a partial word recognition process where appropriate. Most importantly, there is only a description of a primitive server-based recognizer that only recognizes the user's speech and simply returns certain keywords such as the user's name and travel destination to fill out a dedicated form on the user's machine. Also, the streaming of the acoustic parameters does not appear to be implemented in real-time as it can only take place after silence is detected. Finally, while the reference mentions the possible use of natural language processing (column 9) there is no explanation of how such function might be implemented in a real-time fashion to provide an interactive feel for the user.
Companies such as Nuance Communications and Speech Works which up till now are the leading vendors that supply speech and natural language processing products to the airlines and travel reservations market, rely mainly on statistical and shallow semantics to understand the meaning of what the users says. Their successful strategy is based on the fact that this shallow semantic analysis will work quite well in the specific markets they target. Also to their advantage, these markets require only a limited amount to language understanding.
For future and broader applications such as customer relationship management or intelligent tutoring systems, a much deeper understanding of language is required. This understanding will come from the application of deep semantic analysis. Research using deep semantic techniques is today a very active field at such centers as Xerox Palo Alto Research Center (PARC), IBM, Microsoft and at universities such as Univ. of Pittsburg [Litman, 2002], Memphis [Graesser, 2000], Harvard [Grosz, 1993] and many others.
In a typical language understanding system there is typically a parser that precedes the semantic unit. Although the parser can build a hierarchical structure that spans a single sentence, parsers are seldom used to build up the hierarchical structure of the utterances or text that spans multiple sentences. The syntactic markings that guide parsing inside a sentence is either weak or absent in a typical discourse. So for a dialog-based system that expects to have smooth conversational features, the emphasis of the semantic decoder is not only on building deeper meaning structures from the shallow analyses constructed by the parser, but also on integrating the meanings of the multiple sentences that constitute the dialog.
Up till now there are two major research paths taken in deep semantic understanding of language: informational and intentional. In the informational approach, the focus is on the meaning that comes from the semantic relationships between the utterance-level propositions (e.g. effect, cause, condition) whereas with the intentional approach, the focus is on recognizing the intentions of the speaker (e.g. inform, request, propose).
Work following the informational approach focuses on the question of how the correct inferences are drawn during comprehension given the input utterances and background knowledge. The earliest work tried to draw all possible inferences [Reiger, 1974; Schank, 1975; Sperber & Wilson, 1986] and in response to the problem of combinatorial explosion in doing so, later work examined ways to constrain the reasoning [DeJong, 1977; Schank et al., 1980; Hobbs, 1980]. In parallel with this work, the notions of conversational implicatures (Grice, 1989) and accomodation [Lewis, 1979] were introduced. Both are related to inferences that are needed to make a discourse coherent or acceptable. These parallel lines of research converged into abductive approaches to discourse interpretation [e.g., Appelt & Pollack, 1990; Charniak, 1986; Hobbs et al., 1993; McRoy & Hirst, 1991; Lascarides & Asher, 1991; Lascarides & Oberlander, 1992; Rayner & Alshawi, 1992]. The informational approach is central to work in text interpretation.
The intentional approach draws from work on the relationship between utterances and their meaning [Grice, 1969] and work on speech act theory [Searle, 1969] and generally employs artificial intelligence planning tools. The early work considered only individual plans [e.g., Power, 1974; Perrault & Allen, 1980; Hobbs & Evans, 1980; Grosz & Sidner, 1986; Pollack, 1986] whereas now there is progress on modeling collaborative plans with joint intentions [Grosz & Kraus, 1993; Lochbaum, 1994]. It is now accepted that the intentional approach is more appropriate for conversational dialog-based systems since the collaborative aspect of the dialog has to be captured and retained.
Present research using deep semantic techniques may employ a semantic interpreter which uses prepositions as its input propositions extracted by semantic concept detectors of a grammar-based sentence understanding unit. It then combines these propositions from multiple utterances to form larger units of meaning and must do this relative to the context in which the language was used.
In conversational dialog applications such as an intelligent tutoring system (ITS), where there is a need for a deep understanding of the semantics of language, hybrid techniques are used. These hybrid techniques combine statistical methods (e.g., Latent Semantic Analysis) for comparing student inputs with expected inputs to determine whether a question was answered correctly or not [e.g., Graesser et al., 1999] and the extraction of thematic roles based on the FrameNet [Baker, et al, 1998] from a student input [Gildea & Jurafsky, 2001].
The aforementioned cited articles include:                Appelt, D. & Pollack, M. (1990). Weighted abduction for plan ascription. Menlo Park, Calif.: SRI International. Technical Note 491.        Baker, Collin F., Fillmore, Charles J., and Lowe, John B. (1998): The Berkeley FrameNet project. In Proceedings of the COLING-ACL, Montreal, Canada.        Charniak, E. (1993). Statistical Language Analysis. Cambridge: Cambridge University Press.        Daniel Gildea and Daniel Jurafsky. 2002. Automatic Labeling of Semantic Roles. Computational Linguistics 28:3, 245-288.        DeJong, G. (1977). Skimming newspaper stories by computer. New Haven, Conn.: Department of Computer Science, Yale University. Research Report 104.        FrameNet: Theory and Practice. Christopher R. Johnson et al, http://www.icsi.berkeley.edu/˜framenet/book/book.html        Graesser, A. C., Wiemer-Hastings, P., Wiemer-Hastings, K., Harter, D., Person, N., and the TRG (in press). Using latent semantic analysis to evaluate the contributions of students in AutoTutor. Interactive Learning Environments.         Graesser, A., Wiemer-Hastings, K., Wiemer-Hastings, P., Kreuz, R., & the Tutoring Research Group (2000). AutoTutor: A simulation of a human tutor, Journal of Cognitive Systems Research, 1,35-51.        Grice, H. P. (1969). Utterer's meaning and intentions. Philosophical Review, 68(2):147-177.        Grice, H. P. (1989). Studies in the Ways of Words. Cambridge, Mass.: Harvard University Press.        Grosz, B. & Kraus, S. (1993). Collaborative plans for group activities. In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI '93), Chambery, France (vol. 1, pp. 367-373).        Grosz, B. J. & Sidner, C. L. (1986). Attentions, intentions and the structure of discourse. Computational Linguistics, 12, 175-204.        Hobbs, J. & Evans, D. (1980). Conversation as planned behavior. Cognitive Science 4(4), 349-377.        Hobbs, J. & Evans, D. (1980). Conversation as planned behavior. Cognitive Science 4(4), 349-377.        Hobbs, J., Stickel, M., Appelt, D., & Martin, P. (1993). Interpretation as abduction. Artificial Intelligence 63(1-2), 69-142.        Lascarides, A. & Asher, N. (1991). Discourse relations and defeasible knowledge. In Proceedings of the 29th Annual Meeting of the Association for Computational Linguistics (ACL '91), Berkeley, Calif. (pp. 55-62).        Lascarides, A. & Oberlander, J. (1992). Temporal coherence and defeasible knowledge. Theoretical Linguistics, 19.        Lewis, D. (1979). Scorekeeping in a language game. Journal of Philosophical Logic 6, 339-359.        Litman, D. J., Pan, Shimei, Designing and evaluating an adaptive spoken dialogue system, User Modeling and User Adapted Interaction, 12, 2002.        Lochbaum, K. (1994). Using Collaborative Plans to Model the Intentional Structure of Discourse. PhD thesis, Harvard University.        McRoy, S. & Hirst, G. (1991). An abductive account of repair in conversation. AAAI Fall Symposium on Discourse Structure in Natural Language Understanding and Generation, Asilomar, Calif. (pp. 52-57).        Perrault, C. & Allen, J. (1980). A plan-based analysis of indirect speech acts. American Journal of Computational Linguistics, 6(3-4), 167-182.        Pollack, M. (1986). A model of plan inference that distinguishes between the beliefs of actors and observers. In Proceedings of 24th Annual Meeting of the Association for Computational Linguistics, New York (pp. 207-214).        Power, R. (1974). A Computer Model of Conversation. PhD. thesis, University of Edinburgh, Scotland.        Rayner, M. & Alshawi, H. (1992). Deriving database queries from logical forms by abductive definition expansion. In Proceedings of the Third Conference of Applied Natural Language Processing, Trento, Italy (pp. 1-8).        Reiger, C. (1974). Conceptual Memory: A Theory and Computer Program for Processing the Meaning Content of Natural Language Utterances. Stanford, Calif.: Stanford Artificial Intelligence Laboratory. Memo AIM-233.        Schank, R. (1975). Conceptual Information Processing. New York: Elsevier.        Schank, R., Lebowitz, M., & Birnbaum, L. (1980). An integrated understander. American Journal of Computational Linguistics, 6(1).        Searle, J. (1969). Speech Acts: An Essay in the Philosophy of Language. Cambridge: Cambridge University Press.        Sperber, D. & Wilson, D. (1986). Relevance: Communication and Cognition. Cambridge, Mass.: Harvard University Press.        
The above are also incorporated by reference herein.